package com.example.dynamicprogramming;

/**
 * 10个台阶一次能走一步或两步有多少种走法
 */
public class FootSteps {
    public static void main(String[] args) {
        System.out.println(footSteps(100));
    }

    public static int footSteps(int n){
        if (n<=2){
            return n;
        }
        int [] f=new int[n+1];
        f[0]=0;
        f[1]=1;
        f[2]=2;
        for (int i = 3; i <n+1; i++) {
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }
}
